/**
 * 邻接矩阵图的深度、广度优先算法
*/

#include "MGraph.c"
#include "Queue.c"

#ifndef MGRAPH_DFS_BFS
#define MGRAPH_DFS_BFS
void DFS(MGraph* g, int v, int* visited) {
    visited[v] = 1;
    for (int i=0; i<g->vertexNum; i++) {
        if (g->g[v][i] == 1 && !visited[i]) {
            printf("%d ", i);
            DFS(g, i, visited);
        }
    }
}

void BFS(MGraph* g, int v, int* visited) {
    visited[v] = 1;
    Queue* queue = createQueue();
    enQueue(queue, v);
    while (!isEmptyQueue(queue)) {
        int v = deQueue(queue);
        for (int i=0; i<g->vertexNum; i++) {
            if (g->g[v][i] == 1 && !visited[i]) {
                printf("%d ", i);
                visited[i] = 1;
                enQueue(queue, i);
            }
        }
    }
    freeQueue(queue);
}

void listComponents(MGraph* g, void (*f)(MGraph* g, int v, int* visited)) {
    // 是否访问过的标志数组，0 未访问过，1 访问过
    int* visited = (int*)calloc(g->vertexNum, sizeof(int));
    for (int i=0; i<g->vertexNum; i++) {
        if (!visited[i]) {
            printf("{ %d ", i);
            f(g, i, visited);
            printf("}\n");
        }
    }
    free(visited);
}

#endif
